#include "linklist.h"
#include<stdio.h>
#include<stdlib.h>

//创建一个单链表（只有头节点，不存放数据）
linklist list_create(){
	linklist h =(linklist) malloc(sizeof(listnode));
	if(h == NULL){
		printf("linklist create failed\n");
		return NULL;
	}
	h->data = 0;
	h->next = NULL;
	return h;
}
//往链表尾部插入元素
int list_tail_insert(linklist h, data_t value){
	linklist p, q;
	if(h == NULL){
		printf("linklist is NULL\n");
	}

	//新建一个节点
	p = (linklist)malloc(sizeof(listnode));
	if(p == NULL){
		printf("insert Node failed\n");
		return -1;
	}
	p->data = value;
	p->next = NULL;

	//找到当前链表的最后一个节点
	q = h;
	while(q->next != NULL){
		q = q->next;
	}
	q->next = p;
	return 0;
}

//方案一：按位置插入元素
/*
int list_insert(linklist h, data_t value, int pos){
	linklist p, q;
	if( h == NULL ){
		printf("head is NULL\n");
		return -1;
	}
	if(pos <= -1){
		printf("pos is invalid\n");
		return -1;
	}

	//新建节点
	p = (linklist)malloc(sizeof(listnode));
	if(p == NULL){
		printf("insert Node failed\n");
		return -1;
	}
	p->data = value;
	p->next = NULL;

	//插入节点
	q = h;
	int i = -1;
	while( i < pos){
		if(q == NULL){
			printf("pos is invalid\n");
			return -1;
		}
		if(i + 1 == pos){
			p->next = q->next;
			q->next = p;
		}
		i++;
		q = q->next;
	}
	return 0;
}*/

//方案二：将上述问题拆分成两步，
//1. 获取插入位置前一个结点的指针
//2. 新建一个结点
//3. 将该结点放入链表中
int list_insert(linklist h, data_t value, int pos){
	linklist p, q;
	if(h == NULL){
		printf("pos is invalid\n");
		return -1;
	}
	if(pos <= -1){
		printf("pos is invalid\n");
		return -1;
	}
	//获取插入位置前一个结点的指针
	p = list_get(h, pos-1);
	if(p == NULL){
		printf("pos is invalid\n");	
		return -1;
	}
	//新建节点
	q = (linklist)malloc(sizeof(listnode));
	if(q == NULL){
		printf("insert Node failed\n");
		return -1;
	}
	q->data = value;
	q->next = NULL;
	//放入该结点
	q->next = p->next;
	p->next = q;
	return 0;
}

linklist list_get(linklist h, int pos){
	linklist p;
	if(pos < -1){
		printf("pos is invalid\n");
		return NULL;
	}
	p = h;
	int i = -1;
	while(i < pos){
		if(p == NULL){
			return NULL;
		}
		p = p->next;
		i++;
	}
	return p;
}

int list_show(linklist h){
	linklist p;
	if(h == NULL){
		printf("h is NULL\n");
		return -1;
	}
	p = h;
	while(p->next != NULL){
		printf("%d ",p->next->data);
		p = p->next;
	}
	puts("");
	return 0;
}


/*
 * 为避免野指针，返回一个空指针，重置H
 * */
linklist list_free(linklist h){
	if(h == NULL){
		return NULL;
	}
	linklist  q;
	while(h != NULL){
		q = h->next;
		printf("%d ", h->data);
		free(h);
		h = q;
	}
	puts("");
	return NULL;
	
}
int list_delete(linklist h, int pos){
	linklist p, q;
	if(h == NULL){
		printf("h is NULL\n");
		return -1;
	}
	if(pos <= -1){
		printf("pos is invalid\n");
		return -1;
	}
	p = list_get(h, pos-1);
	if(p == NULL || p->next == NULL){
		printf("pos is invalid\n");
		return -1;
	}

	q = p->next;
	p->next = q->next;
	free(q);
	return 0;
}

//链表的反转
int list_reverse(linklist h){
	linklist p, q;
	if(h == NULL || h->next == NULL || h->next->next == NULL){
		printf("No need reverse\n");
		return -1;
	}
	p = h->next->next;
	h->next->next = NULL;
	while(p != NULL){
		q = p->next;
		p->next = h->next;
		h->next = p;
		p = q;
	}
	return 0;

}
//链表相邻两个节点最大值对应的第一个元素指针 value用来存储两值之和
linklist list_adjmax(linklist h, data_t *value){
	linklist p, q, l;
	if(h == NULL || h->next == NULL || h->next->next == NULL){
		printf("No need reverse\n");
		return NULL;
	}
	p = h->next;
	q = p->next;
	*value = p->data + q->data;
	l = p;
	while(q->next != NULL){
		q = q->next;
		p = p->next;
		if(p->data + q->data > *value){
			*value = p->data + q->data;
			l = p;
		}
	}
	return l;
}
//有序链表的合并，将h2合并到h1链表上
//当前代码有点瑕疵，节点里存在野指针，优化如下：
int list_merge(linklist h1, linklist h2){
	linklist p, q, l;
	//后续代码可以支持空链表
	if(h1 == NULL){
		return -1;
	}
	//后续代码可以支持空链表
	if(h2 == NULL){
		return -1;
	}
	p = h1;
	q = p->next;
	l = h2->next;
	h1->next = NULL;
	h2->next = NULL;//这行代码如果不加，会影响后面节点释放
	while(q != NULL && l != NULL){
		if(q->data > l->data){
			p->next = l;
			l = l->next;
		}else {
			p->next = q;
			q = q->next;
		}
		p = p->next;
		p->next = NULL;//这行代码可要可不要，不过代码规范性还是写上。
	}
	if(q == NULL){
		p->next = l;
	}
	if(l == NULL){
		p->next = q;
	}
	return 0;

}
//链表的排序
int list_sort(linklist h){
	linklist p, q, l;
	if(h == NULL){
		printf("h is NULL\n");
		return -1;
	}
	if( h->next == NULL || h->next->next == NULL){
		printf("No Need Sort\n");
		return -1;
	}
	p = h;
	q = h->next->next;
	h->next->next = NULL;
	while(q != NULL){
		l = q->next;
		while(p->next != NULL){
			if(q->data <= p->next->data){
				q->next = p->next;
				p->next = q;
				break;
			}else{
				p = p->next;
			}
		}
		if(p->next == NULL){
			q->next = NULL;
			p->next = q;
		}
		q = l;
	}
	return 0;
}
